package linked;

import java.util.HashSet;
import java.util.Set;

/**
 * 141. 环形链表
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
 */
public class Problem_141 {

    /**
     * 方法一：哈希表
     * 挨个遍历链表节点，每遍历到一个节点时，判断该节点此前是否被访问过。
     * 具体做法:
     * 我们可以使用哈希表来存储所有已经访问过的节点。
     * 每到一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，直接返回true；
     * 否则，就将该节点加入到哈希表中，继续遍历下一个节点 并重复上述过程。
     * 若可以遍历到链表的末尾，则表示链表无环，最后返回false即可。
     */
    public boolean hasCycle_1(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode listNode = head;
        while (listNode != null) {
            if (set.contains(listNode)) {
                return true;
            }
            set.add(listNode);
            listNode = listNode.next;
        }

        return false;
    }

    /**
     * 方法二：快慢指针
     * 我们定义两个指针，一快一慢。
     * 慢指针每次只移动一步，而快指针每次移动两步(即保证快指针每次都比慢指针多走一步)。
     * 初始时，慢指针在位置 head，而快指针在位置 head.next。
     * 这样一来，如果在移动的过程中，快指针反过来追上了慢指针，则说明该链表为环形链表。
     * 否则，快指针将到达链表尾部，则说明链表无环。
     */
    public boolean hasCycle_2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
